package Simple4;

public class Find5 {

	/**
	 * The basic idea is:
	 * Count the numbers that do not have the digit 5. 
	 * Among the numbers less than 10^k, there are exactly 9^k of them. 
	 * Then it remains to treat the numbers from 10^k to n, where 10^k <= n < 10^(k+1)
	 * 
	 * @param n		The number range [0...n]
	 * @return		The numbers of number contains 5 in the range[0...n]
	 * 				if n is negative, return -1.
	 */
	public static int numOfFive(int n){
		if(n<0){
			System.out.println("The number input must more than 0.");
			return -1;
		}
		int ret = 0;
		int n_clone = n;
		int powOfTen = 1,powCount = 0;
		while(powOfTen<=n/10){
			powOfTen *= 10;
			powCount++;
		}
		
		int pre = 0;
		while(powOfTen>0){
			int times = n/powOfTen;
			pre = times;
			if(times>5) 
				times--;
			ret += Math.pow(9, powCount) * times;
			if(pre==5){
				ret--;
				break;
			}
			n = n % powOfTen;
			powCount--;
			powOfTen /= 10;
		}
		return n_clone-ret;
		
	}
	
	
	public static int dummy(int n){
		int ret = 0;
		for(int i=0;i<=n;++i){
			if(i==Integer.MAX_VALUE) break;
			if(containFive(i))
				ret++;
			System.out.println(ret);
		}
		return ret;
	}
	
	private static boolean containFive(int n){
		while(n>0){
			if(n%10==5) return true;
			n = n/10;
		}
		return false;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int test = Integer.MAX_VALUE-1;
		System.out.println(numOfFive(test));
		System.out.println(containFive(test));
		System.out.println(dummy(test));
	}

}
